// 传递二叉树要传根节点

// 前序遍历 ： 先根次序遍历 中左右
// 1.先打印当前 节点
// 2.再打印左边的，
// 3.再打印 右边的
// 中序遍历 ： 中根次序遍历 左中右
// 1.先打印左边 节点
// 2.再打印当前的，
// 3.再打印 右边的
// 后序遍历： 后根次序遍历  左右中
// 1.先打印左边 节点
// 2.再打印 右边的
// 3.再打印当前

function Node(value) {
  this.value = value;
  this.left = null
  this.right = null
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");
var g = new Node("g");
var h = new Node("h");
a.left = b
a.right = c;
b.left = e;
b.right = f;
c.left = g
c.right = h

// 前序遍历 ： abefcgh  // 最好理解 旋转图 

// 中序遍历 :  ebfagch // 为了更好理解 x轴投影顺序依次来

// 后序遍历：  efbghca


// 前序遍历

 function conSole (root) { 
  if(!root) return;
  console.log('前序',root.value)
  conSole(root.left)
  conSole(root.right)
  }

  // conSole(a)


  // 前序遍历

 function midFor (root) { 
  if(!root) return;
  midFor(root.left)
  console.log('中序',root.value)
  midFor(root.right)
  }

  // midFor(a)


    // 后序遍历

 function backFor (root) { 
  if(!root) return;
  backFor(root.left)
  
  backFor(root.right)
  console.log('中序',root.value)
  }

  backFor(a)
  // 1.给出二叉树，写出前中后序遍历
  // 2.写出前序中序后序遍历的代码

  // 3.给出前序中序还原二叉树，要求写出后序遍历
  var qian = ['a', 'c', 'f', 'g', 'b', 'd', 'e'];
  // a cfg bde
  // 中 左 右 a 根节点  a left  c
  // c left f  c right g
  // b left d  b right e
  var zhong = ['f', 'c', 'g', 'a', 'd', 'b', 'e'];
  // 左 中  右
  // fcg a dbe

  // fgc deb a
  function Node(value) {
      this.value = value;
      this.left = null;
      this.right = null;
  }
 function Func1(q,z) { 
   if(q == null || z == null || q.length == 0||z.length == 0) return null;
   let f1 = new Node(q[0]) // 提前定义好 根节点
   let mid = z.indexOf(f1.value) // 获取中序 根节点的index
   console.log(mid)
   // q 左子树
   let qleft = q.slice(1,mid+1)
   let qright = q.slice(mid+1,z.length)
  //  console.log(qleft)
  //  console.log(qright)
   // 获取zhong左子树
   let midleft = z.slice(0,mid)
   // zhong右子树
   let midright = z.slice(mid+1,z.length)
  //  console.log(midleft)
  //  console.log(midright)
   f1.left =  Func1(qleft,midleft)
   f1.right =   Func1(qright,midright)
   return f1
 }
//  console.log(Func1(qian,zhong))
 
  // 4. 给出后序中序还原二叉树，要求写出前序遍历

//   var qian = ['a', 'c', 'f', 'g', 'b', 'd', 'e'];
// var zhong = ['f', 'c', 'g', 'a', 'd', 'b', 'e'];

// function Node(value) {
//     this.value = value;
//     this.left = null;
//     this.right = null;
// }

// function f1(qian, zhong) {
//     if (qian == null || zhong == null || qian.length == 0 || zhong.length == 0 || qian.length != zhong.length) return null;
//     var root = new Node(qian[0]);
//     var index = zhong.indexOf(root.value);//找到根节点在中序遍历中的位置
//     var qianLeft = qian.slice(1, 1 + index);//前序遍历的左子树
//     var qianRight = qian.slice(1 + index, qian.length);//前序遍历的右子树
//     var zhongLeft = zhong.slice(0, index);//中序遍历的左子树
//     var zhongRight = zhong.slice(index + 1, zhong.length);//中序遍历的右子树
//     root.left = f1(qianLeft, zhongLeft);//根据左子树的前序和中序还原左子树并赋值给root.left
//     root.right = f1(qianRight, zhongRight);//根绝右子树的前序和中序还原右子树并赋值给root.right
//     return root;
// }

// var root = f1(qian, zhong);

// console.log(root.left);
// console.log(root.right);

var zhong2 = ['f', 'c', 'g', 'a', 'd', 'b', 'e'];
// a fcg dbe
//   a
//  c  b
// f g d e
var hou1 = ['f', 'g', 'c', 'd', 'e', 'b', 'a'];
// 左 右 中
// 

function Func2(z,h) { 
  if(h == null || z == null || h.length == 0||z.length == 0) return null;
  let f1 = new Node(h[h.length-1]) // 提前定义好 根节点
  let mid = z.indexOf(f1.value) // 获取中序 根节点的index
  console.log(mid)
  // q 左子树
  let hleft = h.slice(0,mid)
  console.log(hleft)
  let hright = h.slice(mid,z.length-1)
  console.log(hright)
  // console.log(qleft)
  // console.log(qright)
  // 获取zhong左子树
  let midleft = z.slice(0,mid)
  // zhong右子树
  let midright = z.slice(mid+1,z.length)
  // console.log(midleft)
  // console.log(midright)
  // console.log(Func2(midleft,hleft))
  f1.left =  Func2(midleft,hleft)
  f1.right =   Func2(midright,hright)
  return f1
}
console.log('中后还原',Func2(zhong2,hou1))
debugger
// debugger
